#include <stdio.h>
#include <stdlib.h>  
#include <math.h>
#include "projet.h"
#include "parser.h"
#include "algo1.h"
#include "cycle3.h"
#include "cycle4.h"


/**
Fonction qui test si une arrête (i,j) appartient a un cycle de longueur 3.
**/
int appartient_cycle_4(int** liens,int nb_terminaux,int i,int j){
  if(appartient_cycle_3(liens,nb_terminaux,i,j)==1)
    return 1;
  else{
    int n;
    int k;
    for(k=0;k<nb_terminaux;k++)
      for(n=0;n<nb_terminaux;n++)
	if(k!=i&&k!=j&&n!=i&&n!=j&&liens[i][n]==1&&liens[j][k]==1&&liens[k][n]==1)
	  return 1;
    return 0;
  }   
}


/**
Fonction qui test si chaque arrêtes d'un graphe appartient a un cycle de longueur 3
**/
int verifie_cycle_4(int** liens,int nb_terminaux){
  int i;
  int j;
  int d[nb_terminaux];
  int pere[nb_terminaux]; 
  for(i=0;i<nb_terminaux;i++)
    for(j=0;j<nb_terminaux;j++)
      if(liens[i][j]==1&&appartient_cycle_4(liens,nb_terminaux,i,j)!=1)
	return 0;
  return 1;
}


void relier_sommet_4(int** liens,int** distances,int nb_terminaux,int a,int b){
  int i;
  int j;
  int imin=-1;
  int jmin;
  int min=-1;

  for(j=0;j<nb_terminaux;j++)
    for(i=0;i<nb_terminaux;i++)
      if(j!=b&&j!=a&&i!=b&&i!=a&&liens[b][j]==1&&liens[a][i]==1&&(min==-1||distances[i][j]<min)){
	min=distances[i][j];
	imin=i;
	jmin=j;
      }
  if(imin == -1){
    for(j=0;j<nb_terminaux;j++)
      if(j!=b&&j!=a&&liens[b][j]==1){
	imin=a;
	jmin=j;
      }
    for(j=0;j<nb_terminaux;j++)
      if(j!=b&&j!=a&&liens[a][j]==1){
	imin=b;
	jmin=j;
      }
  }
  liens[imin][jmin] = 1;
  liens[jmin][imin] = 1;
} 

void creation_des_cycles_4(int** liens,int** distances,int nb_terminaux){
  int i;
  int j;
  int k;
  for(i=0;i<nb_terminaux;i++)
    for(j=0;j<nb_terminaux;j++)
      if(liens[i][j]==1&&appartient_cycle_4(liens,nb_terminaux,i,j)==0){
	relier_sommet_4(liens,distances,nb_terminaux,i,j);
      }
}	

